package J3_18;

import java.util.*;

public class test {

    //给你一个 值互不相同 的二叉树的根节点 root 。
    //
    //在一步操作中，你可以选择 同一层 上任意两个节点，交换这两个节点的值。
    //
    //返回每一层按 严格递增顺序 排序所需的最少操作数目。
    //
    //节点的 层数 是该节点和根节点之间的路径的边数。
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public int minimumOperations(TreeNode root) {
        if (root == null || root.left == null || root.right == null) {
            return 0;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> arr = new ArrayList();
            while (size != 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                arr.add(node.val);
                size--;
            }
            count += swapCount(arr);
        }
        return count;

    }
    public int swapCount(ArrayList<Integer> arr) {
        int len = arr.size();
        if (len == 1) {
            return 0;
        }
        ArrayList<Integer> arr2 = new ArrayList<>(arr);
        Collections.sort(arr2);
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            map.put(arr2.get(i),i);
        }
        boolean[] visited = new boolean[len];
        int loop = 0;
        for (int i = 0; i < len; i++) {
            if (!visited[i]) {
                int j = i;
                while (!visited[j]) {
                    int index = map.get(arr.get(j));
                    visited[j] = true;
                    j = index;
                }
                loop++;
            }

        }
        return len - loop;
    }

}
